#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<string>
  struct TreeNode {
     int val;
    TreeNode *left;
   TreeNode *right;
  };
  void PreOrder(TreeNode* root, string& str) {
      if (root == nullptr) {
          return;
      }
      str += to_string(root->val);
      if (root->left == root->right&&root->left == nullptr) {
          return;
      }
      else if (root->left == nullptr && root->right != nullptr) {
          str += '(', str += ')';
          str += '(';
          PreOrder(root->right, str);
          str += ')';
      }
      else if (root->right == nullptr && root->left != nullptr) {
          str += '(';
          PreOrder(root->left, str);
          str += ')';
      }
      else {
          str += '(';
          PreOrder(root->left, str);
          str += ')';
          str += '(';
          PreOrder(root->right, str);
          str += ')';
      }
  }
    string tree2str(TreeNode* root) {
        string str;
        PreOrder(root, str);
        return str;
    }
    int main()
    {
        TreeNode n1, n2, n3, n4;
        n1.val = 1;
        n2.val = 2; n1.left = &n2;
        n3.val = 3; n1.right = &n3;
        n2.left = nullptr; n2.right = &n4;
        n4.val = 4; n4.left = nullptr;
        n4.right = nullptr; n3.left = n3.right = nullptr;
        string str;
        str=tree2str(&n1);
        cout << str << endl;
        return 0;
    }